package com.neusoft.search.interpolation;

/**
 * @Author lichunlong lcl253137@alibaba-inc.com
 * @Desc 插值查找: 在二分查找的基础上，通过插值公式进行优化（计算middle的公式优化）
 * @Date 2024-11-24
 */
public class InterpolationSearch {

    public static int interpolationSearch(int[] arr, int target) {
        return interpolationSearch(arr, 0, arr.length - 1, target);
    }

    public static int interpolationSearch(int[] arr, int leftIndex, int rightIndex, int findVal) {
        if (leftIndex > rightIndex || findVal < arr[0] || findVal > arr[arr.length - 1]) {
            return -1;
        }
        // 插值算法的精髓: 对于数据量较大,关键字分布比较均匀的查找表来说,采用插值查找,速度较快
        int middleIndex = leftIndex + (rightIndex - leftIndex) * (findVal - arr[leftIndex]) / (arr[rightIndex] - arr[leftIndex]);

        if (findVal > arr[middleIndex]) {
            // 向右递归
            return interpolationSearch(arr, middleIndex + 1, rightIndex, findVal);
        } else if (findVal < arr[middleIndex]) {
            // 向左递归
            return interpolationSearch(arr, leftIndex, middleIndex - 1, findVal);
        } else {
            return middleIndex;
        }
    }

}
